package com.qfedu.entity.course01;

public class MyLinkedList2<E> {
    //头节点
    private Node<E> head = new Node<E>();
    //尾节点
    private Node<E> tail = head;
    //长度
    private int length = 0;

    /**
     * 在尾部追加节点
     *
     * @param e
     */
    public void insertAtLast(E e) {
        //创建新节点
        //将新节点 挂接到 链表尾节点之后
        tail.next = new Node<>(e);
        //新节点成为 新的尾节点
        tail = tail.next;
        //链表长度+1
        length++;
    }

    public void insertAtFirst(E e) {
        final Node<E> newNode = new Node<>(e);
        //原链表第一个节点
        final Node<E> oldFirst = head.next;
        //头节点指向新创建的节点
        head.next = newNode;
        //新创建节点指向 原链表的第一个节点
        newNode.next = oldFirst;
        //原链表是否为空
        if (head == tail) {
            tail = newNode;
        }
        length++;
    }

    public E getByIndex(int index) {
        //判断索引是否越界
        if (index < 0 || index >= length) {
            return null;
        }
        //当前节点
        Node<E> node = head.next;
        //当前位置
        int pos = 0;
        //遍历位置到目标索引
        while (pos != index) {
            //将下一个节点作为当前节点
            // 因为已经做过越界判断，所以这里不需要再判断是否到达尾节点
            node = node.next;
            //当前位置+1
            pos++;
        }
        //返回查找位置的值
        return node.item;
    }

    public void insertAtIndex(int index, E val) {
        if (index == 0) {
            //在头部插入
            insertAtFirst(val);
        } else if (index == length) {
            //在尾部插入
            insertAtLast(val);
        } else if (index > 0 && index < length) {
            //查找插入位置的前一个节点
            Node<E> preNode = head.next;
            //当前位置
            int pos = 0;
            //遍历位置到目标位置的前一个节点
            while (pos != (index - 1)) {
                //将下一个节点作为当前节点
                // 因为已经做过越界判断，所以这里不需要再判断是否到达尾节点
                preNode = preNode.next;
                //当前位置+1
                pos++;
            }
            //目标位置的原始节点
            Node<E> oldNode = preNode.next;
            //将目标位置的原始节点作为新节点的后继结点(next)
            Node<E> node = new Node<E>(val, oldNode);
            //目标位置的前一个节点指向新节点
            preNode.next = node;
            //长度修改
            length++;
        }
    }

    public void removeFirst() {
        if (length == 0) {
            return;
        } else if (length == 1) {
            //只有一个节点，删除后变为空链表，需要改变尾指针
            head.next = null;
            tail = head;
            length--;
        } else {
            //通过头指针获取第一个节点
            Node<E> first = head.next;
            //获取第二个节点
            //头指针执行第二个节点（从而实现了对第一个节点的删除）
            head.next = first.next;
            length--;
        }
    }

    public void removeLast() {
        if (length == 0) {
            return;
        } else if (length == 1) {
            //只有一个节点，删除后变为空链表，需要改变尾指针
            head.next = null;
            tail = head;
            length--;
        } else {
            //通过遍历获取到尾部节点的前一个节点
            Node<E> preNode = getPreNode(length - 1);
            preNode.next = null;
            //尾指针指向新的最后一个节点
            tail = preNode;
            length--;
        }

    }

    private Node<E> getPreNode(int index) {
        //判断是否越界
        if (index < 0 || index > length) {
            return null;
        }
        //前一个节点
        Node<E> preNode = head;
        //当前节点
        Node<E> curNode = head.next;
        int pos = 0;
        //遍历是到目标索引
        while (pos != index) {
            //前节点和当前节点都向后移动一个位置
            preNode = curNode;
            curNode = curNode.next;
            pos++;
        }
        //返回目标节点的前一个节点
        return preNode;
    }

    public void removeAtIndex(int index) {
        //判断是否越界
        if (index < 0 || index > length || length == 0) {
            return;
        }
        //获取目标位置的前一个节点
        Node<E> preNode = getPreNode(index);
        //删除的是最后一个节点，也可用 if(tail==preNode.next) 判断
        if (index == length - 1) {
            //更新尾指针
            tail = preNode;
        }
        //通过前一个节点的next找到目标节点，再通过目标节点的next找到后一个节点
        preNode.next = preNode.next.next;
        length--;
    }
}
